package com.lw.leetcode.str.b;

import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 1545. 找出第 N 个二进制字符串中的第 K 位
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/20 16:46
 */
public class FindKthBit {

    public static void main(String[] args) {
        FindKthBit test = new FindKthBit();

        int n = 1 << 20;
        // 0
        int k = 1;


        for (int i = 1; i < 1000000; i++) {
            char a = test.findKthBit(n, i);
            char b = test.findKthBit2(n, i);
            if (a != b) {
                System.out.println(i + "" + a + "" + b);
            }
        }

//        char kthBit = test.findKthBit(0, k);
//        System.out.println(kthBit);
    }

    public char findKthBit(int n, int k) {
        if (k < 3) {
            return (char) (47 + k);
        }
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int index = 2;
        for (int i = 0; i < 20; i++) {
            map.put(index, 1);
            index <<= 1;
        }
        int c = 0;
        while (k != 1) {
            c++;
            k = map.ceilingKey(k) - k;
            if (map.containsKey(k)) {
                return (c & 1) == 0 ? '1' : '0';
            }
        }
        return (c & 1) == 0 ? '0' : '1';
    }

    public char findKthBit2(int n, int k) {
        if (k == 1) {
            return '0';
        }
        int mid = 1 << (n - 1);
        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return findKthBit2(n - 1, k);
        } else {
            k = mid * 2 - k;
            return invert(findKthBit2(n - 1, k));
        }
    }

    public char invert(char bit) {
        return (char) ('0' + '1' - bit);
    }


}
